package top.ivansong92.example.leetcode.learning.common.algorithms.dynamic;


import org.junit.Test;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class TestExample4 {


    public int getMaxLCS(String s1, String s2) {
        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
            return 0;
        }

        return doGetMaxLcs(s1, s1.length() - 1, s2, s2.length() - 1, new Integer[s1.length()][s2.length()]);
    }

    private int doGetMaxLcs(String s1, int s1End, String s2, int s2End, Integer[][] array) {
        if (s1End < 0 || s2End < 0) {
            return 0;
        }

        Integer val = array[s1End][s2End];
        if (val != null) {
            return val;
        }
        char ch1 = s1.charAt(s1End);
        char ch2 = s2.charAt(s2End);
        int res;
        if (ch1 == ch2) {
            res = 1 + doGetMaxLcs(s1, s1End - 1, s2, s2End - 1, array);
        } else {
            res = Math.max(doGetMaxLcs(s1, s1End - 1, s2, s2End, array), doGetMaxLcs(s1, s1End, s2, s2End - 1, array));
        }
        array[s1End][s2End] = res;
        return res;
    }

    public int getMaxLCSV2(String s1, String s2) {
        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
            return 0;
        }
        int s1L = s1.length();
        int s2L = s2.length();

        int[][] resArray = new int[s1L][s2L];
        char ch1 = s1.charAt(0);
        for (int j = 0; j < s2L; j++) {
            int val = s2.charAt(j) == ch1 ? 1 : 0;
            if (j > 0) {
                val = Math.max(resArray[0][j - 1], val);
            }
            resArray[0][j] = val;
        }

        char ch2 = s2.charAt(0);
        for (int i = 0; i < s1L; i++) {
            int val = s1.charAt(i) == ch2 ? 1 : 0;
            if (i > 0) {
                val = Math.max(resArray[i][0], val);
            }
            resArray[i][0] = val;
        }

        for(int i = 1; i < s1L; i ++) {
            ch1 = s1.charAt(i);
            for(int j = 1; j < s2L; j ++) {
                ch2 = s2.charAt(j);
                if (ch1 == ch2) {
                    resArray[i][j] = 1 + resArray[i - 1][j - 1];
                } else {
                    resArray[i][j] = Math.max(resArray[i - 1][j], resArray[i][j - 1]);
                }
            }
        }

        return resArray[s1L - 1][s2L - 1];
    }


    @Test
    public void testrob2V2() {
        System.out.println(getMaxLCSV2("AEBCD", "ABEED"));
    }

    public static String booleanToString(boolean input) {
        return input ? "True" : "False";
    }


    @Test
    public void testEraseOverlapIntervals() {
        System.out.println(eraseOverlapIntervalsV2(new int[][]{{1,2}, {1,3}, {1,4}}));
        System.out.println(eraseOverlapIntervalsV2(new int[][]{{1,2}, {2,3}, {1,4}, {3,4}, {4,7}}));
    }

    /**
     * 435. 无重叠区间
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return 0;
        }
        int len = intervals.length;

        Object[] objArray = Arrays.stream(intervals)
                .sorted((e1, e2) -> {
                    if (e1[0] != e2[0]) {
                        return e1[0] - e2[0];
                    }
                    return e1[1] - e2[1];
                }).toArray();
        for(int i = 0; i < len; i ++) {
            intervals[i] = (int[]) objArray[i];
        }
        int[] array = new int[len];
        Arrays.fill(array, 1);
        int res = 0;
        for(int i = 1; i < len; i ++) {
            int[] a1 = intervals[i];
            int max = 1;
            for(int j = 0; j < i; j ++) {
                if (intervals[j][1] <= a1[0]) {
                    max = Math.max(max, array[j] + 1);
                }
            }
            array[i] = max;
            res = Math.max(max, res);
        }

        return len - res;
    }


    public int eraseOverlapIntervalsV2(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return 0;
        }

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));

        int res = 1;
        int pre = intervals[0][1];
        int len = intervals.length;
        for (int i = 1; i < len; i++) {
            if (intervals[i][0] >= pre) {
                res++;
                pre = intervals[i][1];
            }
        }
        return len - res;
    }


    @Test
    public void testintegerBreak() {
        System.out.println(numSquares(12));
    }

    public int numSquares(int n) {
        if (n <= 1) {
            return 1;
        }

        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }

    private int dsf(int plus, int level, Integer[] visited) {
        Integer v = visited[plus];
        if (v != null) {
            return v;
        }
        int res = Integer.MAX_VALUE;
        int nextLevel = level + 1;
        for (int i = 1; i <= plus; i++) {
            int val = i * i;
            if (val > plus) {
                break;
            }

            if (val == plus) {
                res = level;
                break;
            }

            res = Math.min(res, dsf(plus - val, nextLevel, visited));
        }
        visited[plus] = res;
        return res;
    }

    /**
     * 62. 不同路径
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 63. 不同路径 II
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0][0] == 1) {
            return 0;
        }

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }

        if (m == 1) {
            for (int val : obstacleGrid[0]) {
                if (val == 1) {
                    return 0;
                }
            }
            return 1;
        } else if (n == 1) {
            for (int i = 1; i < m; i++) {
                if (obstacleGrid[i][0] == 1) {
                    return 0;
                }
            }
            return 1;
        }


        long[][] dp = new long[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                continue;
            }
            dp[i][0] = dp[i - 1][0];
        }

        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                continue;
            }
            dp[0][j] = dp[0][j - 1];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return (int) dp[m - 1][n - 1];
    }


    /**
     * 52. N皇后 II
     * @param n
     * @return
     */
    public int totalNQueens(int n) {
        if (n == 1) {
            return 1;
        }
        AtomicInteger res = new AtomicInteger(0);
        soloveNQueens(0, n, res, new ArrayList<>(), new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);
        return res.get();
    }

    private void soloveNQueens(int index, int n, AtomicInteger res, List<Integer> list, boolean[] row, boolean[] a1, boolean[] a2) {
        if (list.size() == n) {
            res.incrementAndGet();
            return;
        }
        int newIndex = index + 1;
        for(int i = 0; i < n; i ++) {
            int idx1 = index + i, idx2 = index - i + n - 1;
            if (row[i] || a1[idx1] || a2[idx2]) {
                continue;
            }
            row[i] = true;
            a1[idx1] = true;
            a2[idx2] = true;
            list.add(i);
            soloveNQueens(newIndex, n, res, list, row, a1, a2);
            row[i] = false;
            a1[idx1] = false;
            a2[idx2] = false;
            list.remove(list.size() - 1);
        }
    }

    @Test
    public void testCoinChange() {
        System.out.println(coinChange2(new int[]{1,2,5}, 11));
    }

    /**
     * 322. 零钱兑换
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }

        if (amount == 0) {
            return 0;
        }

        int len = coins.length;
        if (len == 1) {
            return amount % coins[0] == 0 ? amount / coins[0] : -1;
        }
        Arrays.sort(coins);

        boolean[] used = new boolean[amount + 1];
        LinkedList<CoinNode> queue = new LinkedList<>();
        queue.addLast(new CoinNode(amount, 0));
        while (!queue.isEmpty()) {
            CoinNode coinNode = queue.removeFirst();
            int nextLevel = coinNode.level + 1;
            used[coinNode.amount] = true;
            for (int i = coins.length - 1; i >= 0; i--) {
                int plus = coinNode.amount - coins[i];
                if (plus < 0 || used[plus]) {
                    continue;
                }
                if (plus == 0) {
                    return nextLevel;
                }
                used[plus] = true;
                queue.addLast(new CoinNode(plus, nextLevel));
            }
        }
        return -1;
    }

    private class CoinNode {
        int amount;
        int level;

        CoinNode(int amount, int level) {
            this.amount = amount;
            this.level = level;
        }
    }

    public int coinChange2(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }

        if (amount == 0) {
            return 0;
        }

        int len = coins.length;
        if (len == 1) {
            return amount % coins[0] == 0 ? amount / coins[0] : -1;
        }

        Arrays.sort(coins);
        if (coins[0] > amount) {
            return -1;
        }
        int[][] dp = new int[len][amount + 1];
        int coin = coins[0];
        for (int i = 1; i <= amount; i++) {
            int plus = i - coin;
            if (plus < 0 || i % coin != 0) {
                dp[0][i] = Integer.MAX_VALUE;
            } else {
                dp[0][i] = i / coin;
            }
        }

        for (int i = 1; i < len; i++) {
            coin = coins[i];
            for (int j = 1; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coin) {
                    int val = dp[i][j - coin];
                    if (val != Integer.MAX_VALUE) {
                        dp[i][j] = Math.min(val + 1, dp[i][j]);
                    }
                }
            }
        }
        return dp[len - 1][amount] == Integer.MAX_VALUE ? -1 : dp[len - 1][amount];
    }


    @Test
    public void testFindMaxForm() {
        System.out.println(findMaxForm3(new String[]{"10", "0001", "111001", "1", "0"}, 5, 3));
    }
    /**
     * 474. 一和零
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0 || (m <= 0 && n <= 0)) {
            return 0;
        }
        int len = strs.length;
        Bag[] bags = new Bag[len];
        boolean matchOne = false;
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int nZero = 0, nOne = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    nZero++;
                } else {
                    nOne++;
                }
            }
            matchOne = matchOne || (nZero <= m && nOne <= n);
            bags[i] = new Bag(str, nZero, nOne);
        }

        if (!matchOne) {
            return 0;
        }

        Integer[][][] array = new Integer[len][m + 1][n + 1];
        for(int i = 0; i < len; i ++) {
            array[i][0][0] = 0;
        }

        return dfs(bags, m, n, 0, len, array);
    }

    private int dfs(Bag[] bags, int m, int n, int index, int max, Integer[][][] array) {
        if (index >= max) {
            return 0;
        }

        Integer val = array[index][m][n];
        if (val != null) {
            return val;
        }

        Bag bag = bags[index];
        val = dfs(bags, m, n, index + 1, max, array);
        if (bag.nZero <= m && bag.nOne <= n) {
            val = Math.max(val, dfs(bags, m - bag.nZero, n - bag.nOne, index + 1, max, array) + 1);
        }
        array[index][m][n] = val;
        return val;
    }

    public int findMaxForm2(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0 || (m <= 0 && n <= 0)) {
            return 0;
        }

        int len = strs.length;
        Bag[] bags = new Bag[len];
        boolean matchOne = false;
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int nZero = 0, nOne = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    nZero++;
                } else {
                    nOne++;
                }
            }
            matchOne = matchOne || (nZero <= m && nOne <= n);
            bags[i] = new Bag(str, nZero, nOne);
        }

        if (!matchOne) {
            return 0;
        }

        int[][][] array = new int[len][m + 1][n + 1];

        Bag bag = bags[0];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (bag.nZero <= i && bag.nOne <= j) {
                    array[0][i][j] = 1;
                }
            }
        }
        for (int i = 1; i < len; i++) {
            bag = bags[i];
            for (int k = 0; k <= m; k++) {
                for (int j = 0; j <= n; j++) {
                    array[i][k][j] = array[i - 1][k][j];
                    if (bag.nZero <= k && bag.nOne <= j) {
                        array[i][k][j] = Math.max(array[i][k][j], array[i - 1][k - bag.nZero][j - bag.nOne] + 1);
                    }
                }
            }
        }
        return array[len - 1][m][n];
    }

    public int findMaxForm3(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0 || (m <= 0 && n <= 0)) {
            return 0;
        }

        int len = strs.length;
        Bag[] bags = new Bag[len];
        boolean matchOne = false;
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int nZero = 0, nOne = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    nZero++;
                } else {
                    nOne++;
                }
            }
            matchOne = matchOne || (nZero <= m && nOne <= n);
            bags[i] = new Bag(str, nZero, nOne);
        }

        if (!matchOne) {
            return 0;
        }

        int[][] array = new int[m + 1][n + 1];

        Bag bag;

        for (int i = 0; i < len; i++) {
            bag = bags[i];
            for (int k = m; k >= bag.nZero; k --) {
                for (int j = n; j >= bag.nOne; j --) {
                    array[k][j] = Math.max(array[k][j], array[k - bag.nZero][j - bag.nOne] + 1);
                }
            }
        }
        return array[m][n];
    }


    private class Bag {
        String str;
        int nZero;
        int nOne;

        Bag(String str, int nZero, int nOne) {
            this.str = str;
            this.nOne = nOne;
            this.nZero = nZero;
        }
    }

    /**
     * 139. 单词拆分
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return false;
        }
        Map<String, Boolean> map = new HashMap<>();
        return doWordBreak(s, new HashSet<>(wordDict), map);
    }

    private boolean doWordBreak(String sub, Set<String> wordSet, Map<String, Boolean> map) {
        if (sub.length() == 0 || wordSet.contains(sub)) {
            return true;
        }

        Boolean res = map.get(sub);
        if (res != null) {
            return res;
        }
        res = false;
        for(int i = 1; i < sub.length() && !res; i ++) {
            String s = sub.substring(0, i);
            if (wordSet.contains(s)) {
                res = res || doWordBreak(sub.substring(i), wordSet, map);
            }
        }
        map.put(sub, res);
        return res;
    }

    /**
     * 377. 组合总和 Ⅳ
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target <= 0) {
            return 0;
        }

        Arrays.sort(nums);
        if (nums[0] > target) {
            return 0;
        }
        int len = nums.length;
        int[][] array = new int[len][target + 1];
        int val = nums[0];
        array[0][0] = 1;
        for (int j = 0; j <= target; j++) {
            if (j >= val && j % val == 0) {
                array[0][j] = 1;
            }
        }

        for (int i = 1; i < len; i++) {
            val = nums[i];
            for (int j = 0; j <= target; j++) {
                array[i][j] = array[i - 1][j];
                if (j >= val) {
                    int m = 0;
                    for (int k = 0; k <= i; k++) {
                        m += array[i][j - nums[k]];
                    }
                    array[i][j] = m;
                }
            }
        }
        return array[len - 1][target];
    }

    @Test
    public void testFindTargetSumWays() {
        System.out.println(findTargetSumWays(new int[]{0,0,0}, 0));
    }

    /**
     * 494. 目标和
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0] == target || nums[0] == -target ? 1 : 0;
        }
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }

        if (sum < target || sum < -target || (sum + target) % 2 != 0) {
            return 0;
        }

        int t = (sum + target) / 2;
        Arrays.sort(nums);
        int zeroEnd = 0;
        int multiple = 1;
        for (int i = 0; i < len; i ++) {
            if (nums[i] > 0) {
                zeroEnd = i;
                break;
            }
            multiple = 2 * multiple;
        }

        if (t == 0) {
            return multiple;
        }

        int[] cpNums = new int[len - zeroEnd];
        System.arraycopy(nums, zeroEnd, cpNums, zeroEnd, len);

        AtomicInteger count = new AtomicInteger(0);
        dfs(cpNums, 0, t, count, new boolean[len]);
        return count.get() * multiple;
    }

    private void dfs(int[] nums, int start, int target, AtomicInteger count, boolean[] visited) {
        if (target == 0) {
            count.incrementAndGet();
            return;
        }

        for (int i = start; i < nums.length; i++) {
            if (nums[i] > target) {
                break;
            }

            if ((visited[i] || (i > start && nums[i] == nums[i - 1] && visited[i - 1]))) {
                continue;
            }
            visited[i] = true;
            dfs(nums, i + 1, target - nums[i], count, visited);
            visited[i] = false;
        }
    }

    public int findTargetSumWays2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0] == target || nums[0] == -target ? 1 : 0;
        }
        AtomicInteger count = new AtomicInteger(0);
        dfs2(nums, 0, target, 0, count);
        return count.get();
    }

    private void dfs2(int[] nums, int index, int target, int cur, AtomicInteger count) {
        if (index == nums.length) {
            if (target == cur) {
                count.incrementAndGet();
            }
            return;
        }
        dfs2(nums, index +1, target, cur + nums[index], count);
        dfs2(nums, index +1, target, cur - nums[index], count);
    }

    @Test
    public void testmaxProduct() {
        System.out.println(maxProduct(new int[]{2,3,-2,4}));
    }

    /**
     * 152. 乘积最大子数组
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        int[][] array = new int[len][2];
        array[0][0] = nums[0];
        array[0][1] = nums[0];
        int res = nums[0];
        for (int i = 1; i < len; i++) {
            int a1 = array[i - 1][0] * nums[i];
            int a2 = array[i - 1][1] * nums[i];
            array[i][0] = Math.max(a2, Math.max(nums[i], a1));
            array[i][1] = Math.min(a2, Math.min(nums[i], a1));
            res = Math.max(array[i][0], res);
        }
        return res;
    }


    /**
     * 剑指 Offer 46. 把数字翻译成字符串
     * @param num
     * @return
     */
    public int translateNum(int num) {
        if (num < 10) {
            return 1;
        }

        String numStr = num + "";
        int len = numStr.length();
        int[] array = new int[len];
        array[0] = 1;
        int a1 = numStr.charAt(0) - '0';
        int a2 = numStr.charAt(1) - '0';
        if (a1 == 0 || a1 >= 3 || (a1 == 2 && a2 >= 6)) {
            array[1] = 1;
        } else {
            array[1] = 2;
        }

        for(int i = 2; i < len; i ++) {
            int last = numStr.charAt(i - 1) - '0';
            int cur = numStr.charAt(i) - '0';
            if (last == 0 || last >= 3 || (last == 2 && cur >= 6)) {
                array[i] = array[i - 1];
            } else {
                array[i] = array[i - 1] + array[i - 2];
            }
        }

        return array[len - 1];
    }

    @Test
    public void testmovingCount() {
        System.out.println(movingCount(11,8, 16));
    }

    /**
     * 剑指 Offer 13. 机器人的运动范围
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int movingCount(int m, int n, int k) {
        if ((m == 0 && n == 0) || k < 0) {
            return 0;
        }

        if (k == 0) {
            return 1;
        }

        int[][] array = new int[m][n];
        for(int j = 1; j < n; j ++) {
            array[0][j] = array[0][j - 1] + 1;
        }

        for(int i = 1; i < m; i ++) {
            array[i][0] = array[i - 1][0] + 1;
        }

        for(int i = 1; i < m; i ++) {
            for(int j = 1; j < n; j ++) {
                array[i][j] = Math.min(array[i][j-1], array[i-1][j]) + 1;
            }
        }

        int res = 0;
        for(int i = 0; i < m; i ++) {
            for(int j = 0; j < n; j ++) {
                if (array[i][j] <= k) {
                    res ++;
                }
            }
        }
        return res;
    }

}